package com.leet.code.simple_array;

import java.util.HashMap;
import java.util.Map;

/**
 * @description:
 * @author: WYG
 * @time: 2020/12/17 9:28
 */
public class RelativeSortArray {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        //使用计数排序
        //寻找arr1中的最大值
        int upper = 0;
        for (int x : arr1) {
            upper = Math.max(upper, x);
        }
        //根据arr1的最大值创建数组,存储arr1中元素出现的次数
        int[] frequency = new int[upper + 1];
        for (int x : arr1) {
            ++frequency[x];
        }
        //存放结果的数组
        int[] ans = new int[arr1.length];
        int index = 0;
        //将arr1中在arr2中出现的元素根据其出现次数写入结果数据中
        for (int x : arr2) {
            for (int i = 0; i < frequency[x]; ++i) {
                ans[index++] = x;
            }
            //写入结果数组后该位置置为0
            frequency[x] = 0;
        }
        //将arr1中剩余的没出现在arr2中的元素根据其出现次数插入结果数组中
        for (int x = 0; x <= upper; ++x) {
            for (int i = 0; i < frequency[x]; ++i) {
                ans[index++] = x;
            }
        }
        return ans;
    }

    public int[] My_RelativeSortArray(int[] arr1, int[] arr2) {
        //采用冒泡排序,自定义排序规则
        Map<Integer, Integer> map = new HashMap<>();
        //首先将数组arr2种元素的相对位置插入map种保存
        for (int i = 0; i < arr2.length; i++) {
            map.put(arr2[i], i);
        }
        //进行排序
        for (int i = 0; i < arr1.length; i++) {
            for (int j = 0; j < arr1.length - 1 - i; j++) {
                int a = arr1[j];
                int b = arr1[j + 1];
                //如果两个元素都在
                if (map.containsKey(a) && map.containsKey(b) && map.get(a) > map.get(b)) {
                    arr1[j] = b;
                    arr1[j + 1] = a;
                }
                if (!map.containsKey(a) && map.containsKey(b)) {
                    arr1[j] = b;
                    arr1[j + 1] = a;
                }
                if (!map.containsKey(a) && !map.containsKey(b) && a > b) {
                    arr1[j] = b;
                    arr1[j + 1] = a;
                }
            }
        }
        return arr1;
    }
}
